/*
 * CCVisu is a tool for visual graph clustering
 * and general force-directed graph layout.
 * This file is part of CCVisu.
 *
 * Copyright (C) 2005-2011  Dirk Beyer
 *
 * CCVisu is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * CCVisu is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with CCVisu; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Please find the GNU Lesser General Public License in file
 * license_lgpl.txt or http://www.gnu.org/licenses/lgpl.txt
 *
 * Dirk Beyer    (firstname.lastname@uni-passau.de)
 * University of Passau, Bavaria, Germany
 */
package org.sosy_lab.ccvisu.clustering;

import java.util.LinkedList;
import java.util.List;
import java.util.logging.Level;

import org.sosy_lab.ccvisu.graph.GraphData;
import org.sosy_lab.ccvisu.graph.GraphVertex;
import org.sosy_lab.ccvisu.graph.Group;
import org.sosy_lab.ccvisu.graph.Group.GroupKind;
import org.sosy_lab.ccvisu.graph.RadiusOfGroup;
import org.sosy_lab.common.LogManager;

/**
 * Cluster a given graph with the following algorithm:
 *  1. Create one partition for each node.
 *  2. Repeat until only k partitions are left:
 *    Merge the two partitions with the shorted distance
 *    between their barycenters.
 */
public class ClustererMinDist extends ClustererBase {

  /** Partition the graph in n clusters in a run. */
  protected final int numberOfClusters;

  /**
   *
   * @param graph
   * @param numberOfClusters
   */
  public ClustererMinDist(GraphData graph, LogManager logger, int numberOfClusters) {
    super(graph, logger);
    this.numberOfClusters = Math.max(1, numberOfClusters);
  }

  /**
   * Merge two clusters.
   * The elements of the first cluster (source) are moved to the second (target).
   * @param source
   * @param target
   */
  protected void mergeClusters(Group source, Group target) {
    List<GraphVertex> sourceNodes = source.getNodes();

    for (int nodeIndex = sourceNodes.size()-1; nodeIndex > -1; nodeIndex--) {
      GraphVertex vertex = sourceNodes.get(nodeIndex);
      target.addNode(vertex);
      source.removeNode(vertex);
    }
  }

  @Override
  protected List<Group> internalCreateClustersOfLayout()
      throws InterruptedException {

    List<Group> clusters = new LinkedList<Group>();
    List<GraphVertex> graphVertices = graphData.getVertices();

    // First step: Create one cluster for each vertex.
    for (GraphVertex graphVertex : graphVertices) {
      Group cluster = new Group("Cluster " + clusters.size(), graphData);
      cluster.addNode(graphVertex);
      cluster.setKind(GroupKind.CLUSTER);
      clusters.add(cluster);
    }

    // Aggregate cluster until there are only k clusters left.
    int initialNumOfClusters = clusters.size();

    while (clusters.size() > numberOfClusters) {
      logger.log(Level.INFO, "Num of non-empty clusters: " + clusters.size());
      setProgress(initialNumOfClusters - clusters.size(), initialNumOfClusters, "Running clustering.");

      if (Thread.interrupted()) {
        throw new InterruptedException();
      }

      // Determine pair of clusters with the shortest
      // distance.
      ClusterPair nearestPair = null;
      int nearestPairIndexA = -1;

      for (int i = 0; i < clusters.size(); i++) {
        Group clusterA = (Group) clusters.get(i);

        for (int j = i+1; j < clusters.size(); j++) {
          Group clusterB = (Group) clusters.get(j);

          if (clusterA != clusterB) {
            if ((clusterA.getNodes().size() > 0)
                && (clusterB.getNodes().size() > 0)) {

              ClusterPair pair = new ClusterPair(clusterA, clusterB, null, null);
              double lPairDistance = pair.getEucDistanceBetweenBarycenters();
              if ((nearestPair == null)
                  || (nearestPair.getEucDistanceBetweenBarycenters() > lPairDistance)) {
                nearestPair = pair;
                nearestPairIndexA = i;
              }
            }
          }
        }
      }

      if (nearestPair != null) {
        // Merge the pair of clusters with the smallest distance.
        mergeClusters(nearestPair.clusterA, nearestPair.clusterB);
        clusters.remove(nearestPairIndexA);
      }
    }

    return clusters;
  }

  /**
   * A class to compare two clusters.
   */
  protected static class ClusterPair implements Comparable<ClusterPair> {

    protected final Group         clusterA;
    protected final Group         clusterB;
    protected final Double        distanceOnPairing;
    protected final RadiusOfGroup initialRadiusA;
    protected final RadiusOfGroup initialRadiusB;

    /**
     * @param clusterA   First cluster.
     * @param clusterB   Second cluster.
     */
    public ClusterPair(Group clusterA, Group clusterB,
        RadiusOfGroup initialRadiusA, RadiusOfGroup initialRadiusB) {

      this.clusterA = clusterA;
      this.clusterB = clusterB;
      this.initialRadiusA = initialRadiusA;
      this.initialRadiusB = initialRadiusB;

      if (initialRadiusA != null) {
        distanceOnPairing = calculateEucDistanceBetweenInitialBarycenters();
      } else {
        distanceOnPairing = calculateEucDistanceBetweenActualBarycenters();
      }
    }

    /**
     * Calculate the distance between the barycenters of two clusters in the
     * pair.
     *
     * @return distance.
     */
    protected double calculateEucDistanceBetweenInitialBarycenters() {
      float deltaX = initialRadiusA.getX() - initialRadiusB.getX();
      float deltaY = initialRadiusA.getY() - initialRadiusB.getY();
      float deltaZ = initialRadiusA.getZ() - initialRadiusB.getZ();

      return Math.sqrt(
            (deltaX * deltaX)
          + (deltaY * deltaY)
          + (deltaZ * deltaZ));
    }

    /**
     * Calculate the distance between the barycenters of two clusters in the
     * pair.
     *
     * @return distance.
     */
    protected double calculateEucDistanceBetweenActualBarycenters() {
      float deltaX = clusterA.getX() - clusterB.getX();
      float deltaY = clusterA.getY() - clusterB.getY();
      float deltaZ = clusterA.getZ() - clusterB.getZ();

      return Math.sqrt(
            (deltaX * deltaX)
          + (deltaY * deltaY)
          + (deltaZ * deltaZ));
    }

    /**
     * Get the distance of the pair of clusters.
     * The distance does not get recalculated after changes of assigned nodes!
     *
     * @return distance.
     */
    protected double getEucDistanceBetweenBarycenters() {
      return distanceOnPairing;
    }

    /**
     * Compare two pairs of clusters by their distance.
     */
    @Override
    public int compareTo(ClusterPair compareWith) {

      double compareWithDistance = compareWith.getEucDistanceBetweenBarycenters();
      double thisDistance = getEucDistanceBetweenBarycenters();

      // return signum(thisDistance - compareWithDistance)
      if (compareWithDistance > thisDistance) {
        return -1;
      } else if (compareWithDistance < thisDistance) {
        return 1;
      } else {
        return 0;
      }
    }
  }
}
